package me.project.offer;

/**
 * 求菲波那契数列的第 n 项，n <= 39。
 * f(0) = 0
 * f(1) = 1
 * f(n) = f(n-2) + f(n-1)
 *
 * @author mbryce
 * @date 2018/7/1
 */
public class Solution10_1th_02 {
    private int[] fib = new int[40];

    public Solution10_1th_02(){
        fib[0] = 0;
        fib[1] = 1;

        for (int i = 2; i <= 39; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }

    /**
     * AC
     * 运行时间：27ms
     * 占用内存：9252k
     * O(1) + O(1)
     *
     * 缓存所有的值
     * @param n
     * @return
     */
    public int Fibonacci(int n) {
        return fib[n];
    }

}
